#include "Heap.h"

void HeapInit(HP* heap)
{
	assert(heap);
	heap->a = (HPDataType*)malloc(sizeof(HPDataType) * 4);
	if (heap->a == NULL)
	{
		perror("malloc fail");
		return;
	}
	heap->capacity = 4;
	heap->size = 0;
}

void Swap(HPDataType* x, HPDataType* y)
{
	HPDataType temp = *x;
	*x = *y;
	*y = temp;
}

void AdjustUp(HP* heap, int child)
{
	while (child > 0)
	{
		int parent = (child - 1) / 2;

		if (heap->a[child] > heap->a[parent])
		{
			Swap(&heap->a[child], &heap->a[parent]);
			child = parent;

		}
		else
		{
			break;
		}
	}
}

void HeapPush(HP* heap, HPDataType x)
{
	assert(heap);
	if (heap->size == heap->capacity)
	{
		HPDataType* newnode = (HPDataType*)realloc(heap->a, sizeof(HPDataType) * (heap->capacity) * 2);
		if (newnode == NULL)
		{
			perror("realloc fail");
			return;
		}
		heap->a = newnode;
		heap->capacity *= 2;
	}
	heap->a[heap->size] = x;
	heap->size++;
	int child = heap->size - 1;
	int parent = (child - 1) / 2;

	if (heap->a[child] > heap->a[parent])
	{
		AdjustUp(heap, child);
	}
}


bool HeapEmpty(HP* heap)
{
	return heap->size == 0;
}

void AdjustDown(HPDataType* heap, int size)
{
	int parent = 0;
	int child = parent * 2 + 1;

	if (child + 1 < size && heap[child + 1] > heap[child])
	{
		child++;
	}
	while (child < size)
	{
		if (heap[child] > heap[parent])
		{
			Swap(&heap[child], &heap[parent]);
			parent = child;
			child = child * 2 + 1;
		}
		else
		{
			break;
		}
	}
}


void HeapPop(HP* heap)
{
	assert(heap);
	assert(!HeapEmpty(heap));
	heap->a[0] = heap->a[heap->size - 1];
	heap->size--;
	AdjustDown(heap->a, heap->size);
}

int HeapSize(HP* heap)
{
	assert(heap);
	assert(!HeapEmpty(heap));

	return heap->size;
}

HPDataType HeapTpo(HP* heap)
{
	assert(heap);
	assert(!HeapEmpty(heap));

	return heap->a[0];
}

void HeapDestroy(HP* heap)
{
	assert(heap);
	free(heap->a);
	heap->capacity = 0;
	heap->size = 0;

}
